#pragma once
#include <vector>
#include "huffmantree.cpp"

using std::vector;
using std::pair;

void maxHeapify(vector<pair<char, int> > &weight, int i, int size);

//堆排序函数
void heapSort(vector<pair<char, int> > &weight)
{
	int size = weight.size()-1;
	pair<char, int> temp;
	for(int i = size/2; i >= 0; i--)
		maxHeapify(weight, i, size);
	for(int i = size; i != 0; i--)
	{
		temp = weight[0];
		weight[0] = weight[i];
		weight[i] = temp;
		maxHeapify(weight, 0, i);
	}
}

//堆维护函数
void maxHeapify(vector<pair<char, int> > &weight, int i, int size)
{
	int left = 2*i+1, right = 2*i+2, max;
	pair<char, int> temp;
	max = i;
	if(left < size && weight[left].second > weight[max].second)
		max = left;
	if(right < size && weight[right].second > weight[max].second)
		max = right;
	if(max != i)
	{
		temp = weight[i];
		weight[i] = weight[max];
		weight[max] = temp;
		maxHeapify(weight, max, size);
	}
}

//哈夫曼树构造函数
//算法思想懒得写了
HuffmanTree BuildHuffmanTree(vector<pair<char, int> > dict)
{
	vector<HuffmanTree> forest;
	vector<HuffmanTree>::iterator t;
	HuffmanTree mina, minb;
	vector<pair<char, int> >::iterator cpointer;
	for(cpointer = dict.begin(); cpointer != dict.end(); cpointer++)
	{
		HuffmanTree teTree(*cpointer);
		for(t = forest.begin(); t != forest.end() && (t->root->data.second < cpointer->second); t++);
		forest.insert(t, teTree);
	}
	while(forest.size() > 1)
	{
		mina = forest[0];
		minb = forest[1];
		forest.erase(forest.begin(), forest.begin()+2);
		HuffmanTree temp(mina, minb);
		for(t = forest.begin(); t != forest.end() && (t->root->data.second < temp.Weight()); t++);
		forest.insert(t, temp);
	}
	return forest[0];
}
